using System.Collections.Generic;

namespace Super
{

	/// <summary>
	/// 小顶堆（Max Heap）是一种数据结构，它具有以下特点和作用：
	///特点：

	///小顶堆是一个完全二叉树，其中每个节点的值都大于或等于其子节点的值。
	///小顶堆的根节点是整个堆中的最大值。
	///作用：

	///排序：小顶堆可以用于实现堆排序算法。堆排序是一种高效的排序算法，其基本思想是通过构建小顶堆，然后反复将堆顶元素与最后一个元素交换，然后调整堆使其满足小顶堆的特性，重复此过程直到排序完成。
	///优先级队列：小顶堆可以用作优先级队列的实现。在优先级队列中，每个元素都有一个与之关联的优先级，小顶堆可以根据优先级快速获取最高优先级的元素。
	///Top K 问题：小顶堆可以用于解决 Top K 问题，即从一组数据中找出前 K 个最大或最小的元素。通过维护一个容量为 K 的小顶堆，可以快速找到最大的 K 个元素。
	/// </summary>
	/// <typeparam name="T"></typeparam>
	public class MinHeap<T> where T : IComparable<T>
	{
		public List<T> heap = new List<T>();

		public void BuildHeap(List<T> nodes)
		{
			heap.Clear();
			heap = new List<T>(nodes);

			for (int i = heap.Count / 2 - 1; i >= 0; i--)
			{
				Heapify(i);
			}
		}

		public void Heapify(int index)
		{
			int minIndex = index;
			int leftIndex = index * 2 + 1;
			int rightIndex = index * 2 + 2;

			if (leftIndex < heap.Count && heap[minIndex].CompareTo(heap[leftIndex]) == 1)
				minIndex = leftIndex;

			if (rightIndex < heap.Count && heap[minIndex].CompareTo(heap[rightIndex]) == 1)
				minIndex = rightIndex;

			if (minIndex != index)
			{
				GlobalUtil.ListSwap(heap, minIndex, index);
				Heapify(minIndex);
			}
		}

		public void Insert(T value)
		{
			heap.Add(value);

			int curIndex = heap.Count - 1;
			int parentIndex = (curIndex - 1) / 2;

			while (parentIndex > 0 && heap[curIndex].CompareTo(heap[parentIndex]) == -1)
			{
				GlobalUtil.ListSwap(heap, curIndex, parentIndex);

				curIndex = parentIndex;
				parentIndex = (curIndex - 1) / 2;
			}
		}

		public T RemoveMin()
		{
			if (heap.Count == 0)
				return default(T);

			T result = heap[0];
			heap[0] = heap[heap.Count - 1];

			Heapify(0);

			return result;
		}

		public List<T> HeapSort()
		{
			List<T> result = new List<T>();
			while (heap.Count > 0)
			{
				result.Add(RemoveMin());
			}
			return result;
		}
	}

}
